package com.lry.basic.algorithm.common;

/**
 * @author:刘仁有
 * @desc:
 * @email:953506233@qq.com
 * @data:2019/8/27
 */
// par[x] = x时表示 x的父亲是x
public class UnionFindSet {
    private int par[];
    private int rank[];
    public UnionFindSet(int n){
        par = new int[n];
        rank = new int[n];
        for(int i=0;i<n;i++){
            par[i] = i;
            rank[i] = 0;
        }
    }

    public int find(int x){
        if(par[x]==x) return x;
        else
            return par[x] = find(par[x]);
    }

    public void union(int x,int y){
        x = find(x);
        y = find(y);
        if(x==y)return;

        if(rank[x]<rank[y]){
            par[x] = y;
        }else{
            par[y] = x;
            if(rank[x]==rank[y])
                rank[x]++;
        }
    }

    public boolean isSame(int x,int y){
        return find(x)==find(y);
    }

    public static void main(String[] args) {

    }
}
